package max_area_of_island

var directions = [4][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}

type Pair struct {
	x, y int
}

func maxAreaOfIsland(grid [][]int) int {
	m, n := len(grid), len(grid[0])
	res := 0
	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if 1 == grid[i][j] {
				var cnt int
				var queue []*Pair
				queue = append(queue, &Pair{x: i, y: j})
				for len(queue) > 0 {
					pair := queue[0]
					queue = queue[1:]
					if pair.x < 0 || pair.x >= m || pair.y < 0 || pair.y >= n || grid[pair.x][pair.y] == 0 {
						continue
					}
					cnt++
					grid[pair.x][pair.y] = 0
					for index := 0; index < 4; index++ {
						nextX := directions[index][0] + pair.x
						nextY := directions[index][1] + pair.y
						queue = append(queue, &Pair{x: nextX, y: nextY})
					}
				}
				res = max(res, cnt)
			}
		}
	}
	return res
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}
